package cn.mayday.algorithms.year2020.month8.LRU;

import java.util.HashMap;
import java.util.Map;

/**
 * Leetcode146. LRU缓存机制
 *
 * @author Mayday05
 * @date 2020/8/15 11:31
 */
public class LRUCache {

    class Node {

        int key;

        int value;

        Node next;

        Node pre;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;

    private Map<Integer, Node> map = new HashMap<>();

    private Node headNode, tailNode;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        headNode = new Node(-1, -1);
        tailNode = new Node(-1, -1);

        headNode.next = tailNode;
        tailNode.pre = headNode;
    }


    public int get(int key) {
        if (map.get(key) != null) {
            Node node = map.get(key);
            /**
             * 如果存在，链表移动位置
             */
            moveNode2Head(node);
            return node.value;
        }
        return -1;
    }


    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            // 如果key存在，赋新值，并移动旧节点到Top
            node.value = value;
            moveNode2Head(node);
        } else {
            if (map.size() == capacity) {
                // 删除最后一个(链表和Map都删除掉)
                Node deleteNode = deleteNodeAtEnd();
                // 删除到首部
                map.remove(deleteNode.key);
            }
            // 添加操作相同
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addNode2Head(newNode);
        }
    }

    /**
     * 把当前key指向的结点移到双向链表的头部
     *
     * @param node
     */
    private void moveNode2Head(Node node) {

        // 1、原来 node 的前驱和后继接上
        node.pre.next = node.next;
        node.next.pre = node.pre;

        // 2、再把 node 放在末尾
        addNode2Head(node);
    }

    /**
     * 在双链表的头部新增一个结点
     *
     * @param newNode
     */
    private void addNode2Head(Node newNode) {
        // 1、当前头结点
        Node oldHead = headNode.next;

        // 2、末尾结点的后继指向新结点
        oldHead.pre = newNode;

        // 3、设置新结点的前驱和后继
        newNode.pre = headNode;
        newNode.next = oldHead;

        // 4、更改虚拟头结点的后继结点
        headNode.next = newNode;
    }

    /**
     * 删除双链表尾部结点
     */
    private Node deleteNodeAtEnd() {
        Node oldTail = tailNode.pre;
        Node newTail = oldTail.pre;

        // 两侧结点建立连接
        newTail.next = tailNode;
        tailNode.pre = newTail;

        // 释放引用
        oldTail.pre = null;
        oldTail.next = null;

        return oldTail;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2 /* 缓存容量 */);

        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));       // 返回  1

        cache.put(3, 3);    // 该操作会使得关键字 2 作废

        System.out.println(cache.get(2));       // 返回 -1 (未找到)
        cache.put(4, 4);    // 该操作会使得关键字 1 作废

        System.out.println(cache.get(1));       // 返回 -1 (未找到)

        System.out.println(cache.get(3));       // 返回  3

        System.out.println(cache.get(4));       // 返回  4
    }

    /**
     * 问题分析
     *
     * LRU特点
     *
     * 1、添加时，如果存在，将新值添加到最前面
     *          如果不存在，如果容量够，直接放在最前面
     *                    如果容量不够，删除存在时间最长未更新的
     *
     *2、查询时， 如果存在，快速返回结果并走一遍添加流程可以
     *          如果不存在，按照约定，返回-1即可
     *
     * 综上，队列比较适合存储先后顺序，但是队列查询又比较慢
     */
}
